package com.hare.harelearn.DataStructure.structure.单链表存储结构;

import com.alibaba.fastjson.JSON;

import java.util.Objects;

/**
 * 单链表操作
 */
public class NodeOperator {

    // 头指针
    private static Node head = new Node(null);

    public static void main(String[] args) {
        try {
            Node node0 = new Node("node0", "java");
            Node node1 = new Node("node1", "go");
            Node node2 = new Node("node2", "python");
            Node node3 = new Node("node3", "vue");
            Node node4 = new Node("node4", "php");

            if (head.getNext() == null) {
                head.setNext(node0);
            }

            node0.setNext(node1);
            node1.setNext(node2);
            node2.setNext(node3);
            node3.setNext(node4);
            node4.setNext(null);

            getNode(node3);

            // 删除第一个结点
            //deleteFirstNode();

            // 删除最后一个结点
            //deleteLastNode();

            // 删除指定结点
            //deleteIndexNode(node2);

            // 插入链表
            Node node5 = new Node("node5", "react");
            //insertNode(node5, 3);


            // 插入
            //addFirst(node5);
            //addLast(node5);

            // 删除
            //removeLast();

            // 获取
            System.out.println("获取指定元素" + contains(node5));

            get(3);


            // 反转单链表
            nodeReversal();

        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

    }


    /**
     * 每次插入到头部
     * 头插法
     *
     * @param node
     */
    public static void addFirst(Node node) {
        Node next = head.getNext();
        node.setNext(next);
        head.setNext(node);
        System.out.println(JSON.toJSONString(head));
    }


    /**
     * 每次插入到尾部
     * 尾插法
     *
     * @param node
     */
    public static void addLast(Node node) {
        Node next = head.getNext();
        while (next != null) {
            if (next.getNext() == null) {
                next.setNext(node);
                break;
            }
            next = next.getNext();
        }
        System.out.println(JSON.toJSONString(head));
    }


    /**
     * 删除第一个元素
     */
    public static void removeFirst() throws Exception {
        if (empty()) {
            throw new Exception("空链表~无法删除");
        }
        head.setNext(head.getNext().getNext());
    }


    /**
     * 删除最后一个元素
     */
    public static void removeLast() throws Exception {
        if (empty()) {
            throw new Exception("空链表~无法删除");
        }

        Node temp = null;
        Node next = head.getNext();
        while (next != null) {
            if (next.getNext() == null) {
                temp.setNext(null);
                break;
            }
            temp = next;
            next = next.getNext();
        }
        System.out.println("删除最后一个元素" + JSON.toJSONString(head));
    }


    /**
     * 获取第一个元素
     */
    public static void getFirst() throws Exception {
        Node next = head.getNext();
        System.out.println(JSON.toJSONString(next));
    }


    /**
     * 获取最后一个元素
     */
    public static void getLat() throws Exception {
        Node next = head.getNext();
        while (next != null) {
            next = next.getNext();
        }
        System.out.println("获取链表最后一个元素" + JSON.toJSONString(next));
    }

    /**
     * 查询包含是否存在元素
     */
    public static boolean contains(Node node) throws Exception {
        Node next = head.getNext();
        while (next != null) {
            if (next.getName().equals(node.getName())) {
                return true;
            }
            next = next.getNext();
        }
        return false;
    }

    /**
     * 返回链表中指定索引的元素
     */
    public static void get(Integer index) throws Exception {
        if (index < 0 || index >= size()) {
            throw new Exception("索引越界");
        }

        Node next = head.getNext();
        while (index > 0) {
            next = next.getNext();
            --index;
        }

        System.out.println("获取指定索引元素" + JSON.toJSONString(next.getName()));
    }


    /**
     * 查询指定结点
     * 链表没有下标，只能从头开始依次遍历。直到找到指定结点。
     *
     * @param node
     * @return
     */
    public static boolean getNode(Node node) {
        if (empty()) {
            return false;
        }
        // 获取第一个结点
        Node headNode = head.getNext();
        while (!Objects.isNull(headNode)) {
            if (headNode.getName().equals(node.getName())) {
                System.out.println("已找到指定节点:" + node.getName());
                return true;
            }
            headNode = headNode.getNext();
        }
        return false;
    }

    /**
     * 删除第一个结点
     * 链表存储结构删除很方便，只要更改指针指向即可。
     *
     * @param
     * @return
     */
    public static void deleteFirstNode() {
        Node next = head.getNext();
        head.setNext(next.getNext());
        System.out.println(JSON.toJSONString(head));
    }

    /**
     * 删除最后一个结点
     * 循环找到最后一个结点(最后一个结点的next为null)，保存最后一个的前继结点 设置为null
     */
    public static void deleteLastNode() {
        Node next = head.getNext();
        Node temp = null;
        while (next != null) {
            if (next.getNext() == null) {
                temp.setNext(null);
                break;
            }
            temp = next;
            next = next.getNext();
        }
        System.out.println(JSON.toJSONString(head));
    }

    /**
     * 删除指定结点
     *
     * @param node
     */
    public static void deleteIndexNode(Node node) throws Exception {
        if (empty()) {
            throw new Exception("链表为null无法删除");
        }

        Node next = head.getNext();
        Node temp = null;
        while (next != null) {
            if (next.getName().equals(node.getName())) {
                temp.setNext(next.getNext());
                break;
            }
            temp = next;
            next = next.getNext();
        }
    }


    /**
     * 插入结点
     *
     * @param node  插入结点
     * @param index 插入结点位置索引
     */
    public static void insertNode(Node node, Integer index) {
        int j = 1;
        Node next = head.getNext();
        Node temp = null;
        Integer nodeLength = size();
        while (next != null) {
            if (index == j) {
                if (index == 1) {
                    head.setNext(node);
                    node.setNext(temp);
                    break;
                } else if (j == nodeLength) {
                    temp.setNext(node);
                    node.setNext(next);
                } else if (j == index) {
                    temp.setNext(node);
                    node.setNext(next);
                }
            }
            temp = next;
            next = next.getNext();
            ++j;
        }
        System.out.println(JSON.toJSONString(head));
    }









    /**
     * 获取链表长度
     *
     * @return
     */
    public static Integer size() {
        Node next = head.getNext();
        int length = 0;
        while (next != null) {
            ++length;
            next = next.getNext();
        }
        return length;
    }

    /**
     * 判断链表是否为空
     * 判断头指针是否为null即可
     */
    public static boolean empty() {
        if (null == head.getNext()) {
            return true;
        }
        return false;
    }


    /**
     * 单链表反转
     * 1->2->3->4->5->null
     * 5->4->3->2->1->null
     */
    public static void nodeReversal() {
        Node next = head.getNext();
        Node node = next;
        Node temp = null;
        // 循环遍历链表
        while (next != null) {
            next = next.getNext();
            node.setNext(temp);
            temp = node;
            node = next;
        }
        head.setNext(temp);
        System.out.println("链表反转" + JSON.toJSONString(head));
    }
}
